package com.cat.dataStructure03;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/count-good-numbers/
 * @create 2025/11/10 20:15
 * @since JDK17
 */
// 快速幂
public class Solution40 {
    public int countGoodNumbers(long n) {
        long ans = 1, N = (int) 1e9 + 7, m = n / 2, x = 20;
        while (m != 0) {
            if ((m & 1) != 0) {
                ans = (ans * x) % N;
            }
            x = (x * x) % N;
            m >>= 1;
        }
        if (n % 2 != 0) {
            ans = (ans * 5) % N;
        }

        return ((int) ans);
    }
}
